//#region 下降路径系列
/**931. 下降路径最小和
 * - 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
 * - 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
 * - 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
 * - https://leetcode.cn/problems/minimum-falling-path-sum/description/
 */
export function minFallingPathSum(matrix: number[][]): number {
    // //思路： 第0行已知，从第一行开始，计算当前节点值 + 上一个合法位置的最小路径值
    // const length = matrix.length
    // /**从第0行到 [i][j]，最小路径值 */
    // const dp = Array.from({ length }, () => new Array<number>(length).fill(Infinity))
    // dp[0] = matrix[0] //第0行已知
    // for (let i = 1; i < length; i++) {
    //     for (let j = 0; j < length; j++) {
    //         //计算和当前节点“相邻”的 （上左、正上、上右 一共三个）
    //         for (let k = j - 1; k <= j + 1; k++) {
    //             if (k < 0 || k >= length) continue
    //             dp[i][j] = Math.min(dp[i - 1][k] + matrix[i][j], dp[i][j]) // 当前节点值 + 上一个合法位置的最小路径值
    //         }
    //     }
    // } 
    // return Math.min(...dp[length - 1])

    //根据上面的代码可以发现，“只依赖上一行数组”，所以我们可以使用滚动数组，降低空间复杂度 （从 O(n*n) 降低到 O(2n) ）
    const length = matrix.length
    let dp = [...matrix[0]]
    const temp = [...matrix[0]] //需要用临时数组，否则会影响到dp数组
    for (let i = 1; i < length; i++) {
        for (let j = 0; j < length; j++) {
            //计算和当前节点“相邻”的 （上左、正上、上右 一共三个）
            let min = Infinity
            for (let k = j - 1; k <= j + 1; k++) {
                if (k < 0 || k >= length) continue
                min = Math.min(min, dp[k] + matrix[i][j])// 当前节点值 + 上一个合法位置的最小路径值 
            }
            temp[j] = min
        }
        dp = [...temp]  //遍历结束后才能更新dp （不然在计算 min 的时候，就会改变了dp）
    }
    return Math.min(...dp)
}
/** 1289. 下降路径最小和 II
 * - 给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
 * - https://leetcode.cn/problems/minimum-falling-path-sum-ii/description/ 
 */
export function minFallingPathSum2(grid: number[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]): number {
    //和普通下降路径的区别：只可以斜着下降，但是可以不用相邻 

    // // 时间复杂度 O(n^3) 空间复杂度 O(n^2)
    // const length = grid.length
    // const dp = Array.from({ length }, () => new Array<number>(length).fill(Infinity))
    // dp[0] = [...grid[0]]
    // for (let i = 1; i < length; i++) {
    //     for (let j = 0; j < length; j++) {
    //         let min = Infinity
    //         for (let k = 0; k < length; k++) {
    //             if (j === k) continue
    //             min = Math.min(dp[i - 1][k] + grid[i][j], min)
    //         }
    //         dp[i][j] = min
    //     }
    // }
    // return Math.min(...dp[length - 1])

    // 时间复杂度 O(n^3) 空间复杂度 使用题目传入的空间
    const length = grid.length
    for (let i = 1; i < length; i++) {
        for (let j = 0; j < length; j++) {
            let min = Infinity
            for (let k = 0; k < length; k++) {
                if (j === k) continue
                min = Math.min(grid[i - 1][k] + grid[i][j], min)
            }
            grid[i][j] = min
        }
    }
    return Math.min(...grid[length - 1])
}
/**2304. 网格中的最小路径代价
 * （和上面的比起来，就是在下降的过程中，除了踩到节点需要花费钱，还需要花费额外路费）
 * - 详细描述看 https://leetcode.cn/problems/minimum-path-cost-in-a-grid/description/
 */
export function minPathCost(grid: number[][], moveCost: number[][]): number {
    const m = grid.length
    const n = grid[0].length
    const dp = Array.from({ length: m }, () => new Array<number>(n).fill(Infinity))
    dp[0] = [...grid[0]] //第一行的代价已知

    //从1开始遍历，找到 “上一个节点到我这的最小代价” 
    for (let i = 1; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let min = Infinity
            const nowNode = grid[i][j];//当前节点
            for (let k = 0; k < moveCost[nowNode].length; k++) {
                const cost = moveCost[grid[i - 1][k]][j] //上一个节点到当前节点的代价 
                min = Math.min(min, dp[i - 1][k] + cost)
            }
            dp[i][j] = nowNode + min //赋值加上当前节点值
        }
    }

    return Math.min(...dp[m - 1])
}
//#endregion